#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    void AdjustUp(vector<int>& vi, int child)
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            if (vi[parent] > vi[child])
                swap(vi[parent], vi[child]);
            else
                break;
            child = parent;
            parent = (child - 1) / 2;
        }
    }

    void AdjustDown(vector<int>& vi, int parent)
    {
        int child = parent * 2 + 1;
        while (child < vi.size())
        {
            if ((child + 1 < vi.size()) && (vi[child] > vi[child + 1]))
                child++;
            if (vi[parent] > vi[child])
                swap(vi[parent], vi[child]);
            else
                break;
            parent = child;
            child = 2 * parent + 1;
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        vector<int> vi;
        vi.resize(k);
        for (int i = 0; i < k; i++)
            vi[i] = nums[i];
        for (int i = (k - 2) / 2; i >= 0; i--)
        {
            AdjustDown(vi, i);
        }
        for (int i = k; i < nums.size(); i++)
        {
            if (nums[i] > vi[0])
            {
                vi[0] = nums[i];
                AdjustDown(vi, 0);
            }
        }
        return vi[0];
    }
};

class Solution {
public:
    int qsort(vector<int>& nums, int left, int right, int k)
    {
        int key = left + rand() % (right - left + 1);
        swap(nums[key], nums[left]);
        int n = nums[left], begin = left, end = right;
        for (int i = left; i <= right;)
        {
            if (nums[i] < n) swap(nums[left++], nums[i++]);
            else if (nums[i] == n) i++;
            else swap(nums[right--], nums[i]);
        }
        if (k <= end - right) return qsort(nums, right + 1, end, k);
        else if (k <= end - left + 1) return n;
        else return qsort(nums, begin, left - 1, k - (end - left + 1));
    }
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned int)time(nullptr));
        return qsort(nums, 0, nums.size() - 1, k);
    }
};